/** 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 53. 最大子序和  https://leetcode-cn.com/problems/maximum-subarray/
 */
package com.chen.Leet;

import java.util.Arrays;

public class Array_53 {
	// 解题思路来源：https://leetcode-cn.com/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
	// 讲解了动态规范的方法，推荐
	static int maxSubArray(int[] nums) {
		int len = nums.length;
		// dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
		int[] dp = new int[len];
		dp[0] = nums[0];

		for (int i = 1; i < len; i++) {
			if (dp[i - 1] > 0) {
				dp[i] = dp[i - 1] + nums[i];
			} else {
				dp[i] = nums[i];
			}
		}

		// 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
		int res = dp[0];
		for (int i = 1; i < len; i++) {
			res = Math.max(res, dp[i]);
		}
		return res;
		
	}

	public static void main(String[] args) {
	
		int nums[] = { 1, 3, 5, 6 };
		int target = 2;
		System.out.println();
	}

}
